package code;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class Code212 {
	

	
	public boolean dfs(char[][] board,int x,int y,int[][] vis,int cnt,String word,int idx){
		char c=word.charAt(idx);
		/*
		 * 查找x,y的相邻位置是否有合适的元素
		 */
		if(c!=board[x][y])
			return false;
		if(idx==word.length()-1)
			return true;
		for(int i=0;i<4;i++){
			int tx=x+dir[i][0];
			int ty=y+dir[i][1];
			if(tx>=0 && tx<n && ty>=0 && ty<m && vis[tx][ty]!=cnt){
				vis[tx][ty]=cnt;
				if(dfs(board,tx,ty,vis,cnt,word,idx+1))
					return true;
				vis[tx][ty]=cnt-1;
			}
		}
		return false;
	}
	
	public boolean findWord(char[][] board,String word){
		int i,j;
		
		int[][] vis=new int[n][m];
		/*
		 * 记录每次遍历的记录，这样就不需要每次都去初始化vis，只需要每次遍历的时候，增加cnt的值就OK
		 */
		int cnt=0;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				/*
				 * 先找到起点字母，然后开始遍历
				 */
				if(board[i][j]==word.charAt(0)){
					cnt++;
					/*
					 * 起点为x=i,y=j
					 */
					vis[i][j]=cnt;
					if(dfs(board,i,j,vis,cnt,word,0))
						return true;
				}
			}
		}
		return false;
	}
	
    public List<String> findWordsII(char[][] board, String[] words) {
    	List<String> result=new ArrayList<String>();
    	Set<String> set=new HashSet<String>();
    	
    	int num=words.length;
    	n=board.length;
    	if(n==0)
    		return result;
    	
    	m=board[0].length;
    	for(int i=0;i<num;i++){
    		if(set.contains(words[i]))
    			continue;
    		set.add(words[i]);
    		if(findWord(board,words[i]))
    			result.add(words[i]);
    	}
        return result;
    }
    
    /*
     * 以上的做法TLE了
     * 改成将所有的单词，建成字典树
     * 再枚举每一个点[i,j]作为起点的能覆盖的单词是什么
     * 
     */
    /**
     * ****************************这里开始************
     */
	private int[][] dir={{0,1},{0,-1},{1,0},{-1,0}};
	
	private int n,m;
	
    class Tire{
    	int val;
    	boolean isWord;
    	Tire[] children;
    	boolean has;
    	Tire(int x){
    		val=x;
    		isWord=false;
    		has=false;
    		children=new Tire[26];
    		for(int i=0;i<26;i++){
    			children[i]=null;
    		}
    	}
    }
    /*
     * 根节点
     */
    private Tire root=new Tire(-1);
    /*
     * 建树
     */
    
    public void buildTire(String[] words){
    	int n=words.length;
    	Tire p;
    	for(int i=0;i<n;i++){
    		p=root;
    		int len=words[i].length();
    		for(int j=0;j<len;j++){
    			int offSet=words[i].charAt(j)-'a';
    			if(p.children[offSet]==null){
    				Tire node=new Tire(offSet);
    				p.children[offSet]=node;
    			}
    			p=p.children[offSet];
    		}
    		/*
    		 * 末尾节点标记为单词的结尾
    		 */
    		p.isWord=true;
    	}
    }
    /*
     * 从[i,j]节点开始遍历board来表示确定字典树中出现的单词
     */
    public void dfs(int x,int y,char[][] board,int[][] vis,int cnt,Tire p){
    	/*
    	 * 四个方向扩展，但是要注意访问过的，不能重复访问
    	 */
    	if(p==null)
    		return ;
    	/*
    	 * 如果当前的节点是单词，那这个单词就可以到达
    	 */
    	if(p.isWord)
    		p.has=true;
    	for(int i=0;i<4;i++){
    		int tx=x+dir[i][0];
    		int ty=y+dir[i][1];
    		if(tx>=0 && tx<n && ty>=0 && ty<m && vis[tx][ty]!=cnt){
    			int offSet=board[tx][ty]-'a';
    			vis[tx][ty]=cnt;
    			dfs(tx,ty,board,vis,cnt,p.children[offSet]);
    			
    			vis[tx][ty]=cnt-1;
    		}
    	}
    }
    
    public void countWords(Tire p,List<String> result,Stack<Integer> stack){
    	if(p==null)
    		return ;
    	if(p.has){
    		StringBuilder sb=new StringBuilder();
    		for(int i=0;i<stack.size();i++){
    			sb.append((char)(stack.get(i)+'a'));
    		}
    		result.add(sb.toString());
    	}
    	for(int i=0;i<26;i++){
    		if(p.children[i]==null)
    			continue;
    		stack.push(i);
    		countWords(p.children[i], result, stack);
    		stack.pop();
    	}
    }
    
    public List<String> findWords(char[][] board, String[] words) {
    	List<String> result=new ArrayList<String>();
    	Set<String> set=new HashSet<String>();
    	
    	int num=words.length;
    	n=board.length;
    	if(n==0)
    		return result;
    	
    	m=board[0].length;
    	/*
    	 * build Tire
    	 */
    	buildTire(words);
    	/*
    	 * find words
    	 */
    	int cnt=0;
    	int[][] vis=new int[n][m];
    	
    	for(int i=0;i<n;i++){
    		for(int j=0;j<m;j++){
    			cnt++;
    			vis[i][j]=cnt;
    			dfs(i,j,board,vis,cnt,root.children[board[i][j]-'a']);
    		}
    	}
    	/*
    	 * count the words
    	 */
    	countWords(root, result, new Stack<Integer>());
        return result;
    }
    
    public static void main(String[] args){
//    	char[][] board={{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
//    	String[] words={"oath","pea","eat","rain"};
    	char[][] board={{'a','b'},{'c','d'}};
    	String[] words={"acdb"};
    	new Code212().findWords(board, words);
    }
}
